package us.kg.kotoriforest.leetcode.hot100;

/**
 * <a href="https://leetcode-cn.com/problems/word-search/">79. 单词搜索</a>
 *
 * @author Kotori rotroutine@163.com
 * @since 2025/2/25
 */
public class WordSearch {
    // 上下左右
    private int[] dx = {0, 0, -1, 1}, dy = {-1, 1, 0, 0};
    private boolean[][] check;

    public boolean exist(char[][] board, String w) {
        char[] word = w.toCharArray();
        int row = board.length, col = board[0].length;
        check = new boolean[row][col];

        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (dfs(board, word, i, j, 0)) return true;
            }
        }

        return false;
    }

    private boolean dfs(char[][] board, char[] word, int i, int j, int index) {
        if (word[index] != board[i][j]) return false;
        if (index == word.length - 1) return true;

        check[i][j] = true;
        for (int k = 0; k < 4; ++k) {
            int x = i + dx[k], y = j + dy[k];
            if (x < 0 || x == board.length || y < 0 || y == board[0].length || check[x][y]) continue;
            dfs(board, word, x, y, index + 1);
        }
        check[i][j] = false;

        return false;
    }

    public static void main(String[] args) {
        char[][] board = {
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}
        };

        System.out.println(new WordSearch().exist(board, "ABCCED"));
    }
}
